//class Solution {
//public:
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[60][60];
//    int m, n, target;
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        m = image.size(), n = image[0].size(), target = image[sr][sc];
//        if (target == color) return image;
//        dfs(image, sr, sc, color);
//        return image;
//    }
//
//    void dfs(vector<vector<int>>& image, int sr, int sc, int color)
//    {
//        if (vis[sr][sc]) return;
//        image[sr][sc] = color, vis[sr][sc] = true;
//        for (int i = 0; i < 4; i++)
//        {
//            int x = sr + dx[i], y = sc + dy[i];
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && image[x][y] == target)
//                dfs(image, x, y, color);
//        }
//    }
//};



//class Solution {
//public:
//    int ret = 0;
//    int m, n;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[310][310];
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == '1' && vis[i][j] == false)
//                {
//                    ret++;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return ret;
//    }
//
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && vis[x][y] == false && grid[x][y] == '1')
//                dfs(grid, x, y);
//        }
//    }
//};



//class Solution {
//public:
//    int m, n, ret = 0;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[60][60];
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        m = grid.size(), n = grid[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (grid[i][j] == 1 && vis[i][j] == false)
//                    ret = max(ret, dfs(grid, i, j));
//            }
//        }
//        return ret;
//    }
//
//
//    int dfs(vector<vector<int>>& grid, int i, int j)
//    {
//        int ret = 1;
//        vis[i][j] = true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = dx[k] + i, y = dy[k] + j;
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && vis[x][y] == false)
//                ret += dfs(grid, x, y);
//        }
//        return ret;
//    }
//};




//class Solution {
//public:
//    int m, n;
//    int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
//    bool vis[210][210];
//    void solve(vector<vector<char>>& board) {
//        for (int i = 0; i < m; i++)
//        {
//            if (board[i][0] == 'O' && vis[i][0] == false)
//                dfs(board, i, 0);
//            if (board[i][n - 1] == 'O' && vis[i][n - 1] == false)
//                dfs(board, i, n - 1);
//        }
//
//        for (int j = 0; j < n; j++)
//        {
//            if (board[0][j] == 'O' && vis[0][j] == false)
//                dfs(board, 0, j);
//            if (board[m - 1][j] == 'O' && vis[m - 1][j] == false)
//                dfs(board, m - 1, j);
//        }
//
//        for (int i = 1; i < m - 1; i++)
//        {
//            for (int j = 1; j < n - 1; j++)
//            {
//                dfs(board[i][j] == 'O' && vis[m])
//            }
//        }
//    }
//};


